Xilinx, Inc. the assignee of the present application, manufactures FPGAs, the complexity of which continues to increase. Freeman in U.S. Pat. No. Reissue 34,363, incorporated herein by reference, which is a re-issue of original U.S. Pat. No. 4,870,302, describes the first FPGA. An FPGA is an integrated circuit chip which includes a plurality of programmable input/output pads, a plurality of configurable logic elements, and a programmable interconnect structure for interconnecting the plurality of logic elements and pads. Each logic element implements a logic function of the n inputs to the logic element according to how the logic element has been configured. Logic functions may use all n inputs to the logic element or may use only a subset thereof. A few of the possible logic functions that a logic element can be configured to implement are: AND, OR, XOR, NAND, NOR, XNOR and mixed combinations of these functions.
One disclosed implementation of the logic element includes a configurable lookup table which is internal to the logic element and which includes 2.sup.n individual memory cells, where n is the number of input signals the lookup table can handle. At configuration, in this architecture a bitstream programs the individual memory cells of the lookup table with a desired function by writing the truth table of the desired function to the individual memory cells. Although the programming is described as being performed serially, other techniques for parallel programming are also known.
One memory cell architecture appropriate for use in the lookup tables is shown in FIG. 1 and described by Hsieh in U.S. Pat. No. 4,821,233, incorporated herein by reference. A memory cell of this architecture is programmed by applying the value to be written to the memory cell on the data input line, "Data," and strobing the corresponding address line, "ADDR." Further, although this architecture uses five transistors, other known configurations, e.g., six transistor static memory cells, also are appropriate choices for implementing the memory cells of the lookup table. As shown in FIG. 1, inverter 726 may be included to increase the drive of memory cell 700, and avoid effecting the value stored in memory cell 700 unintentionally via charge sharing with the read decoder.
After configuration, to use a lookup table, the input lines of the configured logic element act as address lines which select a corresponding memory cell in the lookup table. For example, a logic element configured to implement a two-input NAND gate would output the corresponding value {1,1,1,0} contained in the one of the four memory cells corresponding to the current input pair {00, 01, 10, 11}, respectively.
This selection is performed by a decoding multiplexer which selects a memory cell from the lookup table on the basis of the logic levels of the input lines. A block diagram of an exemplary four-input lookup table composed of 16 memory cells 700.sub.1 through 700.sub.16 and a decoding multiplexer 200 is shown in FIG. 2. The multiplexer propagates a value stored in one of the memory cells 700.sub.1 -700.sub.16 of the lookup table to an output X of the lookup table as selected by the four input signals F0-F3.
FIG. 3 is a schematic diagram of another embodiment of a lookup table. In this embodiment, the lookup table is implemented using four memory cells 700.sub.1 -700.sub.4 and a two-input decoding multiplexer 200 with two input signals, F0 and F1. The two-input decoding multiplexer 200 is shown in detail as being implemented by a hierarchy of pass transistors which propagate the value stored in the selected memory cell to the output X of the logic element. In FIG. 3, the memory cells may be implemented as shown in FIG. 1.
The above architecture was later augmented to enhance the functionality of the lookup tables. U.S. Pat. No. 5,343,406 to Freeman et al., incorporated herein by reference, describes how additional circuitry can enable lookup tables to behave as random access memories (RAMs) which can be both read and written after configuration of the logic device. When the option of allowing the user to write data to memory cells is available, there also must be provision for entering the user's data into these memory cells and reading from the memory cells. This capability is provided by including two means for accessing each dual function memory cell, one which is used to supply the configuration bitstream from off the chip, and another which is used during operation to storevalues from signals that are routed from the interconnect Lines of the FPGA. FIG. 4 shows the memory cell architecture described in U.S. Pat. No. 5,343,406 which allows memory cell 750 to be programmed both during and after configuration. During configuration, memory cell 750 is programmed using the same process for programming the memory cell of FIG. 1.
After configuration, memory cell 750 is programmed differently. A value to be written to memory cell 750 is applied through the interconnect structure of the FPGA to the second data line 705, and then the corresponding write-strobe line WS for the memory cell is pulsed. This pulse latches the value on line 705 into memory cell 750. Like the lookup table of FIG. 2 which uses a series of memory cells from FIG. 1, a series of memory cells from FIG. 4 are combinable into a lookup table.
FIG. 5 is a block diagram showing a four-input lookup table with synchronous write capability. There is a write strobe generator 504 which receives a clock signal, CK, and a write enable signal, WE, and creates a single write strobe signal, WS, for the lookup table. To write a value to a desired memory cell, say 750.sub.5, the value is applied on line D.sub.in and the address of the desired memory cell 750.sub.5 is applied to the input lines F0-F3 of demultiplexer 500. The value then is latched into the desired memory cell 750.sub.5 by pulsing the write strobe. Conversely, to read a value stored in a different desired memory cell 750.sub.3, the address of the memory cell 750.sub.3 is applied to the input lines F0-F3 of decoding multiplexer 200 (without pulsing the write strobe), as was described with reference to FIGS. 2 and 3.
FIG. 6 is a schematic illustration of a two-input lookup table with synchronous write capability. FIG. 6 includes four memory cells 750.sub.1, through 750.sub.4. Detail of demultiplexer 500 and multiplexer 200 is shown in FIG. 6.
The implementation and operation of other logic array devices are described in "The Programmable Logic Data Book," pages 4-1 to 4-372, copyright 1996 by Xilinx, available from Xilinx, Inc., 2100 Logic Drive, San Jose, Calif. 95124. This portion of "The Programmable Logic Data Book" is incorporated herein by reference.
Because a 4-input lookup table is only capable of storing 16-bits of data, it would be desirable to have an architecture that enables a plurality of lookup tables to be combined to from larger random access memories (RAMs) of selectable sizes. It would also be desirable if this architecture would enable dual-port RAMs of selectable sizes. It would further be desirable if this architecture did not significantly increase the complexity of the configurable logic elements (CLEs) in the FPGA.
One or more 4-input lookup tables, such as those illustrated in FIGS. 2 and 5, are typically used to implement combinatorial function generators in a configuration logic element (CLE). Some CLEs include a function generator to select between the outputs of two 4-input lookup tables in order to enable the CLE to implement any 5-input function. One such CLE, implemented in the Xilinx XC4000-Series FPGAs, is described in pages 4-11 through 4-23 of the Xilinx 1996 Data Book entitled "The Programmable Logic Data Book", available front Xilinx, Inc., 2100 Logic Drive, San Jose, Calif. 95224. The function generator can be replaced by a 2-to-1 multiplexer, with a signal selecting between the outputs of the two 4-input lookup tables, as disclosed in U.S. Pat. No. 5,349,250 entitled "Logic Structure and Circuit for Fast Carry" by Bernard J. New. Replacing the function generator with a 2-to-1 multiplexer still provides any function of up to five inputs and reduces the silicon area required to implement a the function generator. An FPGA using two 4-input lookup tables and a 2-to-1 multiplexer to implement a five input function generator is the XC5200.TM. family of products from Xilinx, Inc. The XC5200 CLE is described in pages 4-188 through 4-190 of the Xilinx 1996 Data Book.
A configurable logic block (CLB) capable of generating 6-input functions is described as implemented in the VIRTEX.TM. FPGAs from Xilinx Inc. This CLB includes two CLE slices, and is described in "The Programmable Logic Data Book 1999" pages 3-1 to 3-60, copyright 1999 by Xilinx, available from Xilinx, Inc., 2100 Logic Drive, San Jose, Calif. 95124.
It would be desirable to have a CLE structure that is capable of efficiently implementing functions larger than 6-input functions. It would further be desirable if this CLE structure is easily expandable, without significantly increasing the complexity of the CLE structure.